/*Bellman Ford 队列优化版 即SPFA

 *

 * 使用一个循环队列，保存当前有哪些点要被更新。 初始时只有起点在队列里。

 * 每次从队列中取出一个点来做，更新这个点周围的点的最短路径值(Relax)。

 * 如果周围有点被更新，且这个点原先不在队列中，则将它入队。队列为空时算法结束。

 *

 * 使用邻接表存储

 */

#include <stdio.h>

#include <string.h>

const long maxnum = 0x7fffffff / 4;

const long maxn = 810;   //最大顶点数

int n;                                  //顶点数目

int m;                                  //边数

struct nodetype
{

    int v;                  //表中顶点

    int l;                   //距离

    nodetype *next;

};

nodetype *map[maxn];   //邻接表

void add_edge ( int a, int b, int l ) //由a向b连一条权为l的边

{
    nodetype *p = new nodetype;
    p->next = map[a];
    p->v = b;
    p->l = l;
    map[a] = p;
}

int Q[maxn * 100];

short inQ[maxn + 10];

void Bellmanford ( int s )

{
    int i;
    int dis[maxn];
    memset ( Q, 0, sizeof ( Q ) );
    memset ( inQ, 0, sizeof ( inQ ) );
    for ( i = 1; i <= n; i++ ) dis[i] = maxnum;
    int h, t;
    h = t = 1;
    Q[1] = s;
    inQ[s] = 1;
    dis[s] = 0;
    int flag = 0;
    int count = 0;
    while ( h <= t )
    {
        int x = Q[h];
        inQ[x] = 0;
        nodetype *p = map[x];
        while ( p != NULL )
        {
            count++;
            if ( p->l + dis[x] < dis[p->v] )
            {
                dis[p->v] = p->l + dis[x];
                if ( !inQ[p->v] )
                {
                    t++;
                    Q[t] = p->v;
                    inQ[p->v] = 1;
                }
            }
            p = p->next;
        }
        h++;
        if ( count > n * m )
        {
            flag = 1;
            break;
        }
    }
    //~ if (flag) 有环
    //dis已经生成
    printf ( "Generated by Bellmanford  %d\n", dis[n] );
}

int main()

{
    freopen ( "SSSP.in", "r", stdin );
    memset ( map, 0, sizeof ( map ) );
    scanf ( "%d %d", &n, &m );
    int i;
    for ( i = 1; i <= m; i++ )
    {
        int a, b, c;
        scanf ( "%d%d%d", &a, &b, &c );
        add_edge ( a, b, c );
    }
    Bellmanford ( 1 );
    return 0;
}
